package leetcode.easy.q110;

import leetcode.util.TreeNode;
import leetcode.util.Utils;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("3,9,20,null,null,15,7 balance:{}", new Solution().isBalanced(Utils.buildTree(3,9,20,null,null,15,7)));
        log.info("1,2,2,3,3,null,null,4,4 balance:{}", new Solution().isBalanced(Utils.buildTree(1,2,2,3,3,null,null,4,4)));
        log.info("[] balance:{}", new Solution().isBalanced(Utils.buildTree()));
    }
}
/*
空节点，高度为-1
叶子节点，高度为0

 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return isBalanced(root.left) && isBalanced(root.right) && (Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return -1;
        } else {
            return Math.max(getHeight(node.left) + 1, getHeight(node.right) + 1);
        }
    }
}